#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
@File Name: 优化_基于元组树的栈_stack3.py
@Author: LT
@Date: 2021/9/27 10:41
# -----------------------------------------------------------------------------------------------------
@Description: 
使用列表切取和顺序扩展的方法实现入栈和出栈。这样做的效率并不是特别高：因为两种操作都要复制封装的列表对象。比如：
    def push(self, obj):
        self.stack = [obj] + self.stack         # 列表头作为栈顶
所以要彻底改变底层的数据结构，使用二叉树来避免对整个栈的复制——每一个元素都记录成一个元组。
# -----------------------------------------------------------------------------------------------------
"""


class Stack:
    def __init__(self, start=[]):
        self.stack = None
        for i in range(-len(start), 0):
            self.push(start[-i - 1])                # 一定是反序存入栈！

    def push(self, node):                           # 树向上方生长
        self.stack = node, self.stack               # 新建元组：(node, tree)

    def pop(self):
        node, self.stack = self.stack               # 弹出就是删除的根元组
        return node                                 # 如果是空就会弹出TypeError

    def empty(self):                                # 判断是否为'None'
        return not self.stack

    def __len__(self):                              # 重载len和not
        length, tree = 0, self.stack
        while tree:
            length, tree = length + 1, tree[1]
        return length

    def __getitem__(self, index):                   # 重载：x[i], in, for
        """元组栈的取索引是最耗时的，因为它需要遍历树"""
        length, tree = 0, self.stack
        while length < index and tree:              # 访问节点并计数
            length, tree = length + 1, tree[1]
        if tree:
            return tree[0]                          # 如果越界就抛出IndexError
        else:
            raise IndexError()

    def __repr__(self):
        return f"[FastStack:{self.stack}]"


if __name__ == '__main__':
    pass
